package oj.hot100;

public class 乘积最大子数组 {
    //动态规划
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        f[0] = g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            if(nums[i-1] > 0) {
                f[i] = Math.max(nums[i-1],f[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],g[i-1]*nums[i-1]);
            }else {
                f[i] = Math.max(nums[i-1],g[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],f[i-1]*nums[i-1]);
            }
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}
